package com.lun.medium;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class KthSmallestElementInABST {
	
	//方法一：我写的递归法（BST的中序遍历）
    public int kthSmallest(TreeNode root, int k) {
    	int[] result = {-1}, count = {0};
    	inorder(root, k, result, count);
        return result[0];
    }
    
    private void inorder(TreeNode root, int k, int[] result, int[] count) {
    	if(root == null || result[0] != -1) return;
    	
    	inorder(root.left, k, result, count);
    	if(++count[0] == k) {
    		result[0] = root.val;
    		return;
    	}
    	inorder(root.right, k, result, count);
    }
    
    //方法二：我写的迭代法
    public int kthSmallest2(TreeNode root, int k) {
    	LinkedList<Object[]> stack = new LinkedList<>();
    	stack.push(new Object[] {root, 0});//0, 1, 2, 3 = 左，中，右，pop
    	
    	int count = 0;
    	while(!stack.isEmpty()) {
    		Object[] arr = stack.peek();
    		TreeNode node = (TreeNode)arr[0];
    		int state = (int)arr[1];
    		
    		if(state == 0) {
    			if(node.left != null)
    				stack.push(new Object[] {node.left, 0});
    			arr[1] = 1;
    		}else if(state == 1) {
    			if(++count == k)
    				return node.val;
    			arr[1] = 2;
    		}else if(state == 2) {
    			if(node.right != null) 
    				stack.push(new Object[] {node.right, 0});
    			arr[1] = 3;
    		}else {
    			stack.pop();
    		}
    	}
    	return -1;
    }
    
    //方法三：别人写的迭代法
    public int kthSmallest3(TreeNode root, int k) {
    	LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode p = root;
        int count = 0;
        
        while(!stack.isEmpty() || p != null) {
            if(p != null) {
                stack.push(p);  // Just like recursion
                p = p.left;   
                
            } else {
               TreeNode node = stack.pop();
               if(++count == k) return node.val; 
               p = node.right;
            }
        }
        
        return -1;
    }
    
}
